/*
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，
如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。
冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。
但这种改进对于提升性能来说并没有什么太大作用。

1. 算法步骤
    a.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    b.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
    c.针对所有的元素重复以上的步骤，除了最后一个。
    d.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

/*
解析：
 1.从第一个数开始依次比较相邻的两个元素，如果左边数大于右边数，则交换位置
 2.第一轮比较结束的时候最后一个元素是最大的一个数
 3.按照步骤一的方法从第一个数开始依次比较相邻两个元素，每一轮比较结束大的数都排在后面去了，所以参加新一轮比较的数是在递减的

举例：
    数组 [2, 8, 5, 9, 4, 7]
    第一轮：从第一个数开始依次比较相邻两个元素，比较的个数为6个
        第1、2号位的元素：2和8比较，2 < 8，不交换位置 数组仍然为 [2, 8, 5, 9, 4, 7]
        第2、3号位的元素：8和5比较，8 > 5, 交换位置 数组变为 [2, 5, 8, 9, 4, 7]
        第3、4号位的元素：8和9比较，8 < 9, 不交换位置 数组仍然为 [2, 5, 8, 9, 4, 7]
        第4、5号位的元素：9和4比较，9 > 4, 交换位置 数组变为 [2, 5, 8, 4, 9, 7]
        第5、6号位的元素：9和7比较，9 > 7, 交换位置 数组变为 [2, 5, 8, 4, 7, 9]
    第二轮：从第一个数开始依次比较相邻两个元素，比较的个数为5个，最后一个元素 9 经过第一轮比较已经确定为6个数中的最大数，所以不用再进行比较
        第1、2号位的元素：2和5比较，2 < 5，不交换位置 数组仍然为 [2, 5, 8, 4, 7, 9]
        第2、3号位的元素：5和8比较，5 < 8, 不交换位置 数组仍然为 [2, 5, 8, 4, 7, 9]
        第3、4号位的元素：8和4比较，8 > 4, 交换位置 数组变为 [2, 5, 4, 8, 7, 9]
        第4、5号位的元素：8和7比较，8 > 7, 交换位置 数组变为 [2, 5, 4, 7, 8, 9]
    第三轮：...
    第四轮：...
    第五轮：...
 */
function bubbleSort(arr) {
    // 外层循环控制循环多少轮
    for (let i = 0; i < arr.length - 1; i++) {
        // 内层循环控制每一轮循坏多少次
        for (let j = 0; j < arr.length - 1 - i; j++) {
            // 如果前者大于后者，则交换位置
            if (arr[j] > arr[j + 1]) { // 降序输出 只需要将这里改为 arr[j] < arr[j + 1]
                let swap = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = swap
            }
        }
    }
    return arr
}

console.log(bubbleSort([9, 1, 5, 4, 12, 33, 0]))
console.log(bubbleSort([9, 1, 5, 4, 12, 33, 0, 5]))
console.log(bubbleSort([9, 1, 5, 4, 12, 33, 0, 12.2, 2.5, 5.3, 4]))

// [ 0, 1, 4, 5, 9, 12, 33 ]
// [ 0, 1, 4, 5, 5, 9, 12, 33 ]
// [ 0, 1, 2.5, 4, 4, 5, 5.3, 9, 12, 12.2, 33 ]
